package algorithm.backtracing;

import util.GsonUtil;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Leetcode : https://leetcode.com/problems/permutations/
 * Difficulty : Medium
 *
 *
 * 参考：
 * https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)
 * （这里有各种解法）
 *
 * 给一个去重的数字集合，找到这个集合元素所有的顺序排列
 * @Author Antony
 * @Since 2018/11/7 14:40
 */
public class Permutations {

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3};
        System.out.println(GsonUtil.toJson(permute_DFS(arr)));
        System.out.println(GsonUtil.toJson(permute_BFS(arr)));
    }


    /**
     * leetcode : 3ms - 82.59%
     * BFS的思路：
     * 比如[1,2,3,4]
     * 那么先取 1 放入集合。集合是 [[1]]
     * 再拿到 2 放入集合中每一个子集的，每一个空位。那么[1] 就可以有 [1,2] 和 [2,1]。此时就是[[1,2],[2,1]]
     * 再拿到 3 按如上方法往里放。
     * 注意，空位是从 index 从 0 到 index=subList.size() 就跟排队插空一样
     * @param nums
     * @return
     */
    public static List<List<Integer>> permute_BFS(int[] nums){
        List<List<Integer>> tmpList = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        tmpList.add(list);
        List<List<Integer>> result = new ArrayList<>();
        backtrack_BFS(result, tmpList, nums, 1);
        return result;
    }

    private static void backtrack_BFS(List<List<Integer>> result, List<List<Integer>> list, int[] nums, int index){
        if(index == nums.length){
            result.addAll(list);
            return;
        }else{
            List<List<Integer>> tmpList = new ArrayList<>(list.size() * (index+1));
            int tmpNum = nums[index];
            for(List<Integer> subList : list){
                for(int i=0; i<=subList.size(); i++){
                    List<Integer> innerList = new LinkedList<>(subList);
                    innerList.add(i,tmpNum);
                    tmpList.add(innerList);
                }
            }
            backtrack_BFS(result, tmpList, nums, index+1);
        }
    }

    /**
     * leetcode : 4ms - 47.75%
     * 相当于树的DFS遍历，其实就是递归法
     * @param nums
     * @return
     */
    public static List<List<Integer>> permute_DFS(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack_DFS(result, new LinkedList<>(), nums);
        return result;
    }


    /**
     * @param list
     * @param tmpList
     * @param nums
     */
    private static void backtrack_DFS(List<List<Integer>> list, List<Integer> tmpList, int[] nums){
        if(tmpList.size() == nums.length){
            list.add(new ArrayList<>(tmpList));
            return;
        }else{
            for(int i=0; i<nums.length; i++){
                if(tmpList.contains(nums[i])){  // 这里拖慢了时间
                    continue;
                }
                tmpList.add(nums[i]);
                backtrack_DFS(list, tmpList, nums);
                tmpList.remove(tmpList.size() - 1); // 这里很重要
            }
        }
    }
}
